package sort;

import java.util.Arrays;


/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-16
 * Time: 14:20
 */


public class BucketSort{

    public static void main(String[] args) throws Exception {
        int[] arr = {-5, -1, -2, -3};
        bucketSort(arr, 5);
        System.out.println(Arrays.toString(arr));
    }


    /**
     *
     * @param arr
     * @param bucketSize 单个桶的容量
     */
    public static void bucketSort(int[] arr, int bucketSize){
        if (arr.length == 0) {
            return;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }
        //方法调用多余，直接int效果相同
        //int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        //根据容量和数的边界值确定桶的个数
        int bucketCount = (int)((maxValue - minValue) / bucketSize) + 1;
        //每个桶的容量先初始为0，后面再扩容
        int[][] buckets = new int[bucketCount][0];
        // 利用映射函数将数据分配到各个桶中
        for (int j : arr) {
           //int index = (int) Math.floor((j - minValue) / bucketSize);
            //桶的下标
            int index = (int)((j - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], j);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length == 0) {//该桶没有存储数据
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            myinsertSort(bucket);
            for (int value : bucket) {//排序后依次返回原数组
                arr[arrIndex++] = value;
            }
        }
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private static int[] arrAppend(int[] arr, int value) {
        //每次进来一个新的数据，扩容1个位置
        arr = Arrays.copyOf(arr, arr.length + 1);
        //新数据放到新数组的末尾
        arr[arr.length - 1] = value;
        return arr;
    }

    private static void myinsertSort(int[] arr) {
        int insertVal;
        int insertIndex;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            arr[insertIndex + 1] = insertVal;
        }
    }
}